package 中等.搜索.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
 */
public class 电话号码的字母组合_17 {

    public static void main(String[] args) {

    }

    private String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    /**
     * 回溯
     */
    public List<String> letterCombinations(String digits) {
        List<String> list = new ArrayList<>();
        if (digits.length() == 0) {
            return list;
        }

        dfs(new StringBuilder(), 0, digits, list);

        return list;
    }

    private void dfs(StringBuilder stringBuilder, int idx, String digits, List<String> list) {
        if (idx == digits.length()) {
            list.add(stringBuilder.toString());
            return;
        }

        for (char c : map[digits.charAt(idx) - '0'].toCharArray()) {
            stringBuilder.append(c);
            dfs(stringBuilder, idx + 1, digits, list);
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
    }

}
